{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort Vowels in a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortVowels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将字符串中的元音字母排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的字符串&nbsp;<code>s</code>&nbsp;，将&nbsp;<code>s</code>&nbsp;中的元素重新 <b>排列</b>&nbsp;得到新的字符串&nbsp;<code>t</code>&nbsp;，它满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>所有辅音字母都在原来的位置上。更正式的，如果满足&nbsp;<code>0 &lt;= i &lt; s.length</code>&nbsp;的下标 <code>i</code>&nbsp;处的&nbsp;<code>s[i]</code>&nbsp;是个辅音字母，那么&nbsp;<code>t[i] = s[i]</code>&nbsp;。</li>\n",
    "\t<li>元音字母都必须以他们的 <strong>ASCII</strong>&nbsp;值按 <strong>非递减</strong>&nbsp;顺序排列。更正式的，对于满足&nbsp;<code>0 &lt;= i &lt; j &lt; s.length</code>&nbsp;的下标 <code>i</code>&nbsp;和 <code>j</code>&nbsp; ，如果&nbsp;<code>s[i]</code> 和&nbsp;<code>s[j]</code>&nbsp;都是元音字母，那么&nbsp;<code>t[i]</code>&nbsp;的 ASCII 值不能大于&nbsp;<code>t[j]</code>&nbsp;的 ASCII 值。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回结果字母串。</p>\n",
    "\n",
    "<p>元音字母为&nbsp;<code>'a'</code>&nbsp;，<code>'e'</code>&nbsp;，<code>'i'</code>&nbsp;，<code>'o'</code>&nbsp;和&nbsp;<code>'u'</code>&nbsp;，它们可能是小写字母也可能是大写字母，辅音字母是除了这 5 个字母以外的所有字母。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"lEetcOde\"\n",
    "<b>输出：</b>\"lEOtcede\"\n",
    "<b>解释：</b>'E' ，'O' 和 'e' 是 s 中的元音字母，'l' ，'t' ，'c' 和 'd' 是所有的辅音。将元音字母按照 ASCII 值排序，辅音字母留在原地。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"lYmpH\"\n",
    "<b>输出：</b>\"lYmpH\"\n",
    "<b>解释：</b>s 中没有元音字母（s 中都为辅音字母），所以我们返回 \"lYmpH\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含英语字母表中的 <strong>大写&nbsp;</strong>和 <strong>小写&nbsp;</strong>字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-vowels-in-a-string](https://leetcode.cn/problems/sort-vowels-in-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-vowels-in-a-string](https://leetcode.cn/problems/sort-vowels-in-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"lEetcOde\"', '\"lYmpH\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        V = ['a','e','i','o','u', 'A', 'E', 'I', 'O', 'U']\n",
    "        chars = [ch for ch in s]\n",
    "        vowels = list()\n",
    "        for ch in s:\n",
    "            if ch in V:\n",
    "                vowels.append(ch)\n",
    "        vowels.sort(key=lambda char:ord(char))\n",
    "        j = 0\n",
    "        for i in range(len(chars)):\n",
    "            if chars[i] in V:\n",
    "                chars[i] = vowels[j]\n",
    "                j += 1\n",
    "        return \"\".join(chars)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        vowel_str = 'AEIOUaeiou'\n",
    "        vowels = {char: 0 for char in vowel_str}\n",
    "        for char in s:\n",
    "            if char in vowels:\n",
    "                vowels[char] += 1\n",
    "        def gen():\n",
    "            i = 0\n",
    "            for char in s:\n",
    "                if char not in vowels:\n",
    "                    yield char\n",
    "                else:\n",
    "                    while vowels[vowel_str[i]] == 0:\n",
    "                        i += 1\n",
    "                    yield vowel_str[i]\n",
    "                    vowels[vowel_str[i]] -= 1\n",
    "        ret = ''\n",
    "        for char in gen():\n",
    "            ret += char\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        pa = 'aeiouAEIOU'\n",
    "        d = {p:0 for p in pa}\n",
    "        for ss in s:\n",
    "            if ss in pa:\n",
    "                d[ss] += 1\n",
    "        ans = ''\n",
    "        r = list(d.items())\n",
    "        r.sort(key=lambda x:x[0], reverse=True)\n",
    "\n",
    "        char, t = r.pop()\n",
    "        for ss in s:\n",
    "            if ss not in pa:\n",
    "                ans += ss\n",
    "            else:\n",
    "                while t == 0:\n",
    "                    char, t = r.pop()\n",
    "                ans += char\n",
    "                t -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        t = 'aeiouAEIOU'\n",
    "        cnt = Counter()\n",
    "        ans = list(s)\n",
    "        for c in s:\n",
    "            if c in t: cnt[c] += 1\n",
    "        \n",
    "        a = sorted(cnt)\n",
    "        i = 0\n",
    "        for k in a:\n",
    "            tmp = cnt[k]\n",
    "            while tmp > 0:\n",
    "                if s[i] in t:\n",
    "                    ans[i] = k\n",
    "                    tmp -= 1\n",
    "                i += 1\n",
    "\n",
    "        return ''.join(ans)\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        yuanyin = {\"A\":0, \"E\":0, \"I\":0, \"O\":0, \"U\":0, \"a\":0, \"e\":0, \"i\":0, \"o\":0, \"u\":0}\n",
    "        st = [0 for i in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in yuanyin:\n",
    "                yuanyin[s[i]] += 1\n",
    "            else:\n",
    "                st[i] = 1\n",
    "        \n",
    "        ss = \"\"\n",
    "        yyin = \"\"\n",
    "        j = 0\n",
    "        for y in yuanyin:\n",
    "            yyin += y * yuanyin[y]\n",
    "        for i in range(len(s)):\n",
    "            if st[i] == 1:\n",
    "                ss += s[i]\n",
    "            else:\n",
    "                ss += yyin[j]\n",
    "                j += 1\n",
    "        \n",
    "        return ss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "vowelSet = set(['A','E','I','O','U','a','e','i','o','u'])\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        vowels = [c for c in s if c in vowelSet]\n",
    "        vowels.sort()\n",
    "\n",
    "        res = ''\n",
    "        p = 0\n",
    "        for c in s:\n",
    "            if c in vowelSet:\n",
    "                res += vowels[p]\n",
    "                p+=1\n",
    "            else:\n",
    "                res += c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        ans = []\n",
    "        vowels = []\n",
    "        d = \"aeiouAEIOU\"\n",
    "        for c in s:\n",
    "            if c in d:\n",
    "                vowels.append(c)\n",
    "        vowels.sort()\n",
    "        i = 0\n",
    "        for c in s:\n",
    "            if c in d:\n",
    "                ans.append(vowels[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                ans.append(c)\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        vowels = {'A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u'}\n",
    "        vw = sorted([c for c in s if c in vowels], reverse=True)\n",
    "        # 下面这个合成句写法比较陌生\n",
    "        return ''.join([vw.pop() if c in vowels else c for c in s])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        vowels = 'aeiouAEIOU'\n",
    "        res = ['' for _ in range(len(s))]\n",
    "        vowel_chars = []\n",
    "        for i, c in enumerate(s):\n",
    "            if c in vowels:\n",
    "                vowel_chars.append(c)\n",
    "            else:\n",
    "                res[i] = c\n",
    "        vowel_chars.sort()\n",
    "        j = 0\n",
    "        for i, c in enumerate(res):\n",
    "            if c == '':\n",
    "                res[i] = vowel_chars[j]\n",
    "                j += 1\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        vowel_letter = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'] \n",
    "        Consonants = []\n",
    "\n",
    "        for letter in s:\n",
    "            if letter in vowel_letter:\n",
    "                Consonants.append(letter)\n",
    "        Consonants = sorted(Consonants)\n",
    "        s = list(s)\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c in vowel_letter:\n",
    "                s[i] = Consonants[j]\n",
    "                j += 1\n",
    "        print(s)\n",
    "        return ''.join(s)\n",
    "\n",
    "\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def sortVowels(self, s):\n",
    "        l, res, cur = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'], [], []\n",
    "        for x in s:\n",
    "            if x in l:\n",
    "                res.append('')\n",
    "                cur.append(x)\n",
    "            else:\n",
    "                res.append(x)\n",
    "        cur.sort()\n",
    "        left = 0\n",
    "        for i in range(len(res)):\n",
    "            if res[i] == '':\n",
    "                res[i] = cur[left]\n",
    "                left += 1\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        N = len(s)\n",
    "        VOWELS = set(\"aeiouAEIOU\")\n",
    "        t = [None for _ in range(N)]\n",
    "        vowels = deque()\n",
    "\n",
    "        for idx, c in enumerate(s):\n",
    "            if c in VOWELS:\n",
    "                vowels.append(c)\n",
    "            else:\n",
    "                t[idx] = c\n",
    "        \n",
    "        vowels = deque(sorted(vowels))\n",
    "        for idx, c in enumerate(t):\n",
    "            if c is None:\n",
    "                vowel = vowels.popleft()\n",
    "                t[idx] = vowel\n",
    "\n",
    "        return ''.join(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        def sort_logic(item):\n",
    "            return ord(item)\n",
    "            pass\n",
    "\n",
    "        map = ['a', 'e', 'i', 'o', 'u','A','E','I','O','U']\n",
    "        sort_list = []\n",
    "        for c in s:\n",
    "            if c in map:\n",
    "                sort_list.append(c)\n",
    "                pass\n",
    "            pass\n",
    "        sort_list = sorted(sort_list, key=sort_logic,reverse=False)\n",
    "        p = 0\n",
    "        t = 0\n",
    "        res = ''\n",
    "        while p < len(s):\n",
    "            if s[p] not in map:\n",
    "                res = res + s[p]\n",
    "                p += 1\n",
    "                continue\n",
    "                pass\n",
    "            res += sort_list[t]\n",
    "            t += 1\n",
    "            p += 1\n",
    "            pass\n",
    "        return res\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        y = 'aeiouAEIOU'\n",
    "        d = {}\n",
    "        tmp = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in y:\n",
    "                tmp.append(s[i])\n",
    "        tmp = sorted(tmp,key = lambda x:ord(x))\n",
    "        num = 0\n",
    "        l = list(s)\n",
    "        for i,j in enumerate(l):\n",
    "            if j in y:\n",
    "                l[i] = tmp[num]\n",
    "                num += 1\n",
    "        return ''.join(l)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        L = len(s)\n",
    "        t = ['']*L\n",
    "        vowels = []\n",
    "        V = \"AEIOUaeiou\"\n",
    "        for i,ch in enumerate(s):\n",
    "            if ch.lower() in V:\n",
    "                vowels.append(ch)\n",
    "            else:\n",
    "                t[i] = ch\n",
    "        i = 0\n",
    "        for v in sorted(vowels,key=lambda vowel: V.index(vowel)):\n",
    "            while i<L and t[i]!='':\n",
    "                i += 1\n",
    "            t[i] = v\n",
    "        return ''.join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        yuan = ['A','E','I','O','U','a','e','i','o','u']\n",
    "        new_str = []\n",
    "        all_yuan = []\n",
    "        # 记录所有的元音位置,并挖空\n",
    "        for c in s:\n",
    "            if c in yuan:\n",
    "                all_yuan.append(c)\n",
    "                new_str.append(' ')\n",
    "            else:\n",
    "                new_str.append(c)\n",
    "        all_yuan = sorted(all_yuan,key = lambda x:ord(x))\n",
    "        count = 0\n",
    "        for i in range(len(new_str)):\n",
    "            if new_str[i] == ' ':\n",
    "                new_str[i] = all_yuan[count]\n",
    "                count += 1\n",
    "        return ''.join(new_str)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        a, b, d, s = list(s), [], Counter(), set('AEIOUaeiou')\n",
    "        for i, c in enumerate(a):\n",
    "            if c in s:\n",
    "                b.append(i)\n",
    "                d[c] += 1\n",
    "        for i, c in zip(b, chain.from_iterable(repeat(k, d.pop(k)) for k in sorted(d))):\n",
    "            a[i] = c\n",
    "        return ''.join(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        cnt = dict.fromkeys('AEIOUaeiou' , 0)\n",
    "        indiecs = []\n",
    "        sl = list(s)\n",
    "        for i , c in enumerate(s):\n",
    "            if c in cnt:\n",
    "                cnt[c] += 1\n",
    "                indiecs.append(i)\n",
    "        \n",
    "        i = 0\n",
    "        for k , v in cnt.items():\n",
    "            for j in range(v):\n",
    "                sl[indiecs[i]] = k\n",
    "                i += 1\n",
    "        \n",
    "        return \"\".join(sl)\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        res = []\n",
    "        cnt = {\"A\": 0, \"E\": 0, \"I\": 0, \"O\": 0, \"U\": 0, \"a\": 0, \"e\": 0, \"i\": 0, \"o\": 0, \"u\": 0}\n",
    "        n = len(s)\n",
    "        reorder = []\n",
    "        for i in range(0, n):\n",
    "            if s[i] in cnt.keys():\n",
    "                cnt[s[i]] = cnt[s[i]] + 1\n",
    "                res.append(\"NULL\")\n",
    "                reorder.append(i)\n",
    "            else:\n",
    "                res.append(s[i])\n",
    "        \n",
    "        rest = []\n",
    "        for k,v in cnt.items():\n",
    "            rest.append(k*v)\n",
    "        restr = \"\".join(sorted(rest))\n",
    "\n",
    "        for i in range(len(restr)):\n",
    "            res[reorder[i]] = restr[i]\n",
    "        \n",
    "        return \"\".join(res)\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "\n",
    "        vi = [ i for i, c in enumerate(s) if c.lower() in ['a', 'e', 'i', 'o', 'u']]\n",
    "\n",
    "        c = [s[i] for i in vi]\n",
    "        c.sort()\n",
    "\n",
    "        ret = list(s)\n",
    "        for i in range(len(c)):\n",
    "            ret[vi[i]] = c[i]\n",
    "        \n",
    "        return ''.join(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        indexs = []\n",
    "        for i, v in enumerate(s):\n",
    "            if v.lower() in \"aeiou\":\n",
    "                indexs.append(i)\n",
    "\n",
    "        indexs.sort(key = lambda x:s[x])\n",
    "        j = 0\n",
    "        t = list(s)\n",
    "        for i, v in enumerate(t):\n",
    "            if v.lower() in \"aeiou\":\n",
    "                t[i] = s[indexs[j]]\n",
    "                j += 1\n",
    "        # print(s)\n",
    "        return \"\".join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        # print(ord('O'))\n",
    "        # print(ord('o'))#小写的ASCII大\n",
    "        se = {'a','e','u','o','i','A','E','I','O','U'}\n",
    "        stack = list(s)\n",
    "        s = []\n",
    "        idx = collections.deque()\n",
    "        for i,c in enumerate(stack):\n",
    "            if c in se:\n",
    "                s.append(c)\n",
    "                idx.append(i)\n",
    "        s.sort()\n",
    "        for i,index in enumerate(idx):\n",
    "            stack[index] = s[i]\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        lst = list(s)\n",
    "        dct = set(\"aeiouAEIOU\")\n",
    "        ind = []\n",
    "        n = len(s)\n",
    "        word = []\n",
    "        for i in range(n):\n",
    "            if s[i] in dct:\n",
    "                ind.append(i)\n",
    "                word.append(s[i])\n",
    "        word.sort()\n",
    "        for i, w in zip(ind, word):\n",
    "            lst[i] = w\n",
    "        return \"\".join(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        vowels = set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])\n",
    "        pos = []\n",
    "        chars = []\n",
    "        s = list(s)\n",
    "        for i, c in enumerate(s):  \n",
    "            if c in vowels:\n",
    "                chars.append(c)\n",
    "                pos.append(i)\n",
    "\n",
    "        chars.sort()\n",
    "        j = 0\n",
    "        for i in pos:\n",
    "            s[i] = chars[j]\n",
    "            j += 1\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortVowels(self, s: str) -> str:\n",
    "        s_list = list(s)\n",
    "        yuan = []\n",
    "        yuan_idx = []\n",
    "        yuan_set = set(['A','E','U','I','O','a','e','i','o','u'])\n",
    "        for idx,tmp_s in enumerate(s_list):\n",
    "            if tmp_s in yuan_set:\n",
    "                yuan.append( tmp_s )\n",
    "                yuan_idx.append(idx)\n",
    "        yuan.sort()\n",
    "        for i in range(len(yuan)):\n",
    "            s_list[ yuan_idx[i] ] = yuan[i]\n",
    "        return ''.join(s_list)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
